import java.util.Scanner;

class Node {

	int data;
	Node next;

	Node(int x) {
		data = x;
		next = null;
	}

	Node(int x, Node t) {
		data = x;
		next = t;
	}
}

public class MySingleList {

	Node head, tail;

	public MySingleList() {
		head = tail = null;
	}

	void append(int x) {
		Node t = new Node(x);
		if (head == null) {
			head = tail = t;
		} else {
			tail.next = t;
			tail = t;
		}
	}

	void taoDS() {
		head = tail = null;
		int x, i = 1;
		Scanner kb = new Scanner(System.in);
		while (true) {
			System.out.print("\nNhap so thu " + (i++) + ":");
			x = kb.nextInt();
			if (x != 0) {
				append(x);
			} else {
				break;
			}
		}

	}

	void them(int x, int k) {
		int i = 1;
		Node t = new Node(x);

		if (k < 1) {
			System.out.print("Khong chen duoc");
			return;
		} else if (k == 1) {
			t.next = head;
			head = t;
		} else {
			Node nodeRef = head;
			while (i < k && nodeRef != null) {
				nodeRef = nodeRef.next;
				i++;
			}
			if (i == k) {
				t.next = nodeRef.next;
				nodeRef.next = t;
			} else {
				tail.next = t;
				tail = t;
			}
		}
	}

	void xoa(int k) {
		if (k < 1) {
			System.out.print("Khong xoa duoc");
			return;
		}
		int i = 1;
		Node nodeRef = head;
		while (i < k && nodeRef != null) {
			nodeRef = nodeRef.next;
			i++;
		}
		if (i == k) {
			Node t = nodeRef.next;
			nodeRef.next = nodeRef.next.next;
			t.next = null;
		} else {
			System.out.print("Vi tri vuot qua spt ds!");
		}
	}

	boolean kiemTraDoiXung() {

		Node nodeRef = head;
		Node t = tail;
		while (nodeRef != t) {
			if (nodeRef.data != t.data) {
				return false;
			}
			Node p = head;
			while (p.next != t) {
				p = p.next;
			}
			if (nodeRef.next != t) {
				nodeRef = nodeRef.next;
				t = p;
			} else
				return true;
		}
		return true;
	}

	@Override
	public String toString() {
		String t = "==>";
		Node p = head;
		while (p != null) {
			t = t + p.data + "==>";
			p = p.next;
		}
		t = t + "null";
		return t;
	}

	public static void main(String[] agrs) {
		MySingleList l = new MySingleList();
		l.taoDS();
		System.out.print("\nDanh sach vua tao:\n" + l);
		if (l.kiemTraDoiXung())
			System.out.print("\nDoi Xung\n");
		else
			System.out.print("\nKhong Doi Xung\n");
	}
}
